//有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，
//5，7，9，15，21。 
//
// 示例 1: 
//
// 输入: k = 5
//
//输出: 9
// 
// Related Topics 堆 队列 数学 
// 👍 60 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class GetKthMagicNumberLcci {
    public static void main(String[] args) {
        Solution solution = new GetKthMagicNumberLcci().new Solution();
        solution.getKthMagicNumber(643);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int getKthMagicNumber(int k) {
        PriorityQueue<Long> pq = new PriorityQueue<>();
        Set<Long> set = new HashSet<>();

        pq.offer(1L);
        int count =0;
        Long cur = new Long(1);

        while (count<k){
            cur = pq.poll();
            if (!set.contains(cur)) {
                System.out.println(cur);
                pq.offer(cur * 3l);
                pq.offer(cur * 5l);
                pq.offer(cur * 7l);
                count++;
                set.add(cur);
            }
        }
        return cur.intValue();
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}